From 5a953eb03b8d2d08c7c727edb603745f3ac51505 Mon Sep 17 00:00:00 2001 From: Alex Crichton Date: Fri, 29 May 2015 18:40:42 -0700 Subject: [PATCH] Optimize crawl_build_deps to not re-traverse deps This function previously, for each dependency, traversed the entire dependency graph. This ended up taking quite a bit of time as a huge amount of hashing was being done (each of which is somewhat nontrivial). This commit alters the logic to instead precompute a table of all the native dependencies that each crate will need, traversing the dependency graph only once instead of repeatedly. This commit takes a noop build of Servo from 2.1s to 0.4s --- src/cargo/ops/cargo_rustc/context.rs | 3 + src/cargo/ops/cargo_rustc/custom_build.rs | 88 ++++++++++++++++++++++- src/cargo/ops/cargo_rustc/mod.rs | 45 ++++-------- tests/test_cargo_compile_custom_build.rs | 2 +- tests/test_cargo_compile_plugins.rs | 3 +- 5 files changed, 103 insertions(+), 38 deletions(-) diff --git a/src/cargo/ops/cargo_rustc/context.rs b/src/cargo/ops/cargo_rustc/context.rs index 2fcde4398..9ea3dfc0b 100644 --- a/src/cargo/ops/cargo_rustc/context.rs +++ b/src/cargo/ops/cargo_rustc/context.rs @@ -36,6 +36,8 @@ pub struct Context<'a, 'cfg: 'a> { Fingerprint>, pub compiled: HashSet<(&'a PackageId, &'a Target, &'a Profile)>, pub build_config: BuildConfig, + pub build_scripts: HashMap<(&'a PackageId, Kind), + Vec<(&'a PackageId, Profile)>>, host: Layout, target: Option, @@ -92,6 +94,7 @@ impl<'a, 'cfg> Context<'a, 'cfg> { fingerprints: HashMap::new(), profiles: profiles, compiled: HashSet::new(), + build_scripts: HashMap::new(), }) } diff --git a/src/cargo/ops/cargo_rustc/custom_build.rs b/src/cargo/ops/cargo_rustc/custom_build.rs index 8518f728f..be426396b 100644 --- a/src/cargo/ops/cargo_rustc/custom_build.rs +++ b/src/cargo/ops/cargo_rustc/custom_build.rs @@ -5,7 +5,7 @@ use std::path::PathBuf; use std::str; use std::sync::Mutex; -use core::{Package, Target, PackageId, PackageSet}; +use core::{Package, Target, PackageId, PackageSet, Profile}; use util::{CargoResult, human, Human}; use util::{internal, ChainError, profile}; @@ -103,8 +103,7 @@ pub fn prepare(pkg: &Package, target: &Target, req: Platform, let id = pkg.package_id().clone(); let all = (id.clone(), pkg_name.clone(), build_state.clone(), build_output.clone()); - let plugin_deps = super::crawl_build_deps(cx, pkg, target, profile, - Kind::Host); + let plugin_deps = super::load_build_deps(cx, pkg, profile, Kind::Host); try!(fs::create_dir_all(&cx.layout(pkg, Kind::Target).build(pkg))); try!(fs::create_dir_all(&cx.layout(pkg, Kind::Host).build(pkg))); @@ -338,3 +337,86 @@ impl BuildOutput { Ok((library_paths, library_links)) } } + +/// Compute the `build_scripts` map in the `Context` which tracks what build +/// scripts each package depends on. +/// +/// The global `build_scripts` map lists for all (package, kind) tuples what set +/// of packages' build script outputs must be considered. For example this lists +/// all dependencies' `-L` flags which need to be propagated transitively. +/// +/// The given set of targets to this function is the initial set of +/// targets/profiles which are being built. +pub fn build_map(cx: &mut Context, targets: &[(&Target, &Profile)]) { + let mut ret = HashMap::new(); + let pkg = cx.get_package(cx.resolve.root()); + for &(target, profile) in targets { + build(&mut ret, Kind::Target, pkg, target, profile, cx); + build(&mut ret, Kind::Host, pkg, target, profile, cx); + } + + // Make the output a little more deterministic by sorting all dependencies + for (&(id, kind), slot) in ret.iter_mut() { + slot.sort_by(|&(p1, _), &(p2, _)| p1.cmp(p2)); + slot.dedup(); + debug!("script deps: {}/{:?} => {:?}", id, kind, + slot.iter().map(|&(s, _)| s.to_string()).collect::>()); + } + cx.build_scripts = ret; + + // Recursive function to build up the map we're constructing. This function + // memoizes all of its return values as it goes along. + fn build<'a, 'b, 'cfg>(out: &'a mut HashMap<(&'b PackageId, Kind), + Vec<(&'b PackageId, Profile)>>, + kind: Kind, + pkg: &'b Package, + target: &Target, + profile: &Profile, + cx: &Context<'b, 'cfg>) + -> &'a [(&'b PackageId, Profile)] { + // If this target has crossed into "host-land" we need to change the + // kind that we're compiling for, and otherwise just do a quick + // pre-flight check to see if we've already calculated the set of + // dependencies. + let kind = if target.for_host() {Kind::Host} else {kind}; + let id = pkg.package_id(); + if out.contains_key(&(id, kind)) { + return &out[&(id, kind)] + } + + // This loop is both the recursive and additive portion of this + // function, the key part of the logic being around determining the + // right `kind` to recurse on. If a dependency fits in the kind that + // we've got specified, then we just keep plazing a trail, but otherwise + // we *switch* the kind we're looking at because it must fit into the + // other category. + // + // We always recurse, but only add to our own array if the target is + // linkable to us (e.g. not a binary) and it's for the same original + // `kind`. + let mut ret = Vec::new(); + for &(pkg, target, p) in cx.dep_targets(pkg, target, profile).iter() { + let req = cx.get_requirement(pkg, target); + + let dep_kind = if req.includes(kind) { + kind + } else if kind == Kind::Target { + Kind::Host + } else { + Kind::Target + }; + let dep_scripts = build(out, dep_kind, pkg, target, p, cx); + + if target.linkable() && kind == dep_kind { + if pkg.has_custom_build() { + ret.push((pkg.package_id(), profile.clone())); + } + ret.extend(dep_scripts.iter().cloned()); + } + } + + let prev = out.entry((id, kind)).or_insert(Vec::new()); + prev.extend(ret); + return prev + } +} diff --git a/src/cargo/ops/cargo_rustc/mod.rs b/src/cargo/ops/cargo_rustc/mod.rs index 579e5a998..e6660ce20 100644 --- a/src/cargo/ops/cargo_rustc/mod.rs +++ b/src/cargo/ops/cargo_rustc/mod.rs @@ -117,6 +117,7 @@ pub fn compile_targets<'a, 'cfg: 'a>(targets: &[(&'a Target, &'a Profile)], let _p = profile::start("preparing build directories"); try!(cx.prepare(pkg, targets)); prepare_init(&mut cx, pkg, &mut queue, &mut HashSet::new()); + custom_build::build_map(&mut cx, targets); } // Build up a list of pending jobs, each of which represent compiling a @@ -330,7 +331,7 @@ fn rustc(package: &Package, target: &Target, profile: &Profile, let rustcs = try!(prepare_rustc(package, target, profile, crate_types, cx, req)); - let plugin_deps = crawl_build_deps(cx, package, target, profile, Kind::Host); + let plugin_deps = load_build_deps(cx, package, profile, Kind::Host); return rustcs.into_iter().map(|(mut rustc, kind)| { let name = package.name().to_string(); @@ -350,8 +351,7 @@ fn rustc(package: &Package, target: &Target, profile: &Profile, let build_state = cx.build_state.clone(); let current_id = package.package_id().clone(); let plugin_deps = plugin_deps.clone(); - let mut native_lib_deps = crawl_build_deps(cx, package, target, - profile, kind); + let mut native_lib_deps = load_build_deps(cx, package, profile, kind); if package.has_custom_build() && !target.is_custom_build() { native_lib_deps.insert(0, current_id.clone()); } @@ -451,35 +451,16 @@ fn rustc(package: &Package, target: &Target, profile: &Profile, } } -fn crawl_build_deps<'a>(cx: &'a Context, - pkg: &'a Package, - target: &Target, - profile: &Profile, - kind: Kind) -> Vec { - let mut deps = HashSet::new(); - visit(cx, pkg, target, profile, kind, &mut HashSet::new(), &mut deps); - let mut ret: Vec<_> = deps.into_iter().collect(); - ret.sort(); - return ret; - - fn visit<'a>(cx: &'a Context, - pkg: &'a Package, target: &Target, profile: &Profile, - kind: Kind, - visiting: &mut HashSet<&'a PackageId>, - libs: &mut HashSet) { - for &(pkg, target, p) in cx.dep_targets(pkg, target, profile).iter() { - if !target.linkable() { continue } - let req = cx.get_requirement(pkg, target); - if !req.includes(kind) { continue } - if !visiting.insert(pkg.package_id()) { continue } - - if pkg.has_custom_build() { - libs.insert(pkg.package_id().clone()); - } - visit(cx, pkg, target, p, kind, visiting, libs); - visiting.remove(&pkg.package_id()); - } - } +fn load_build_deps(cx: &Context, pkg: &Package, profile: &Profile, + kind: Kind) -> Vec { + let pkg = cx.get_package(pkg.package_id()); + let deps = match cx.build_scripts.get(&(pkg.package_id(), kind)) { + Some(a) => a, + None => return Vec::new(), + }; + deps.iter().filter(|&&(_, ref dep_profile)| profile == dep_profile) + .map(|&(x, _)| x.clone()) + .collect() } // For all plugin dependencies, add their -L paths (now calculated and diff --git a/tests/test_cargo_compile_custom_build.rs b/tests/test_cargo_compile_custom_build.rs index 8b1061633..6a2996400 100644 --- a/tests/test_cargo_compile_custom_build.rs +++ b/tests/test_cargo_compile_custom_build.rs @@ -1118,7 +1118,7 @@ test!(build_script_with_dynamic_native_dependency { pub extern fn foo() {} "#); assert_that(build.cargo_process("build"), - execs().with_status(0).with_stderr("")); + execs().with_status(0)); let src = build.root().join("target/debug"); let lib = fs::read_dir(&src).unwrap().map(|s| s.unwrap().path()).find(|lib| { let lib = lib.file_name().unwrap().to_str().unwrap(); diff --git a/tests/test_cargo_compile_plugins.rs b/tests/test_cargo_compile_plugins.rs index 434ffd676..c1a462c0d 100644 --- a/tests/test_cargo_compile_plugins.rs +++ b/tests/test_cargo_compile_plugins.rs @@ -100,7 +100,7 @@ test!(plugin_with_dynamic_native_dependency { pub extern fn foo() {} "#); assert_that(build.cargo_process("build"), - execs().with_status(0).with_stderr("")); + execs().with_status(0)); let src = build.root().join("target/debug"); let lib = fs::read_dir(&src).unwrap().map(|s| s.unwrap().path()).find(|lib| { let lib = lib.file_name().unwrap().to_str().unwrap(); @@ -139,7 +139,6 @@ test!(plugin_with_dynamic_native_dependency { plugin = true "#) .file("bar/build.rs", r#" - #![feature(convert)] use std::path::PathBuf; use std::env; -- 2.30.2